package tree;

public class BinaryTree {
    public static void main(String[] args) {
        BinaryNode root = new BinaryNode(25, "xdq");
        BinaryTrees tree = new BinaryTrees(root);
        BinaryNode node2 = new BinaryNode(2, "lc");
        BinaryNode node3 = new BinaryNode(3, "cbd");
        BinaryNode node4 = new BinaryNode(4, "xzl");
        BinaryNode node5 = new BinaryNode(5, "abc");
        root.left = node2;
        root.right = node3;
        node3.right = node4;
        node3.left = node5;
        tree.preOrder();
    //    tree.infixOrder();
    //    tree.postOrder();
        BinaryNode node = tree.preOrderSerach(5);
        System.out.println("no 为 5 的节点 " + node);
    //    node = tree.preOrderSerach(23);
    //    System.out.println("no 为 23 的节点 " + node);
        tree.dealNode(9);
        tree.preOrder();
        tree.dealNode(3);
        tree.preOrder();
    }
}

class BinaryTrees {
    private BinaryNode root;

    public BinaryTrees(BinaryNode root) {
        this.root = root;
    }

    public void setRoot(BinaryNode root) {
        this.root = root;
    }

    public void preOrder() {
        if (root != null) {
            System.out.println("先序遍历结果：");
            root.preOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    public void infixOrder() {
        if (root != null) {
            System.out.println("中序遍历结果：");
            root.infixOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    public void postOrder() {
        if (root != null) {
            System.out.println("后序遍历结果：");
            root.postOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    public BinaryNode preOrderSerach(int no) {
        if (root != null) {
            return root.preOrderSearch(no);
        } else {
            return null;
        }
    }

    public void dealNode(int no) {
        if (root != null) {
            if (root.no == no) {
                root = null;
                return;
            }
            root.dealNode(no);
        } else {
            System.out.println("树为空，不用删除");
        }
    }
}

class BinaryNode {
    int no;
    String name;
    BinaryNode left;
    BinaryNode right;
    public BinaryNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    @Override
    public String toString() {
        return "BinaryNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    public void preOrder() {
        System.out.println(this);
        if (left != null) {
            this.left.preOrder();
        }
        if (right != null) {
            this.right.preOrder();
        }
    }

    public void infixOrder() {
        if (left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (right != null) {
            this.right.infixOrder();
        }
    }

    public void postOrder() {
        if (left != null) {
            this.left.postOrder();
        }
        if (right != null) {
            this.right.postOrder();
        }
        System.out.println(this);
    }

    public BinaryNode preOrderSearch(int no) {
        if (this.no == no) {
            return this;
        }
        BinaryNode node = null;
        if (this.left != null) {
            node = this.left.preOrderSearch(no);
        }
        if (node != null) {
            return node;
        }
        if (this.right != null) {
            node = this.right.preOrderSearch(no);
        }
        return node;
    }

    public void dealNode(int no) {
        if (this.left != null) {
            if (this.left.no == no) { // 等
                this.left = null;
                return;
            } // 不等
            this.left.dealNode(no);
        }
        // 左为空，看右边
        if (this.right != null) {
            if (this.right.no == no) {
                this.right = null;
                return;
            }
            this.right.dealNode(no);
        }
    }
}
